#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// the current Text under consideration is S[k + i];
// on success, the loop will loop forward by one step, as i is increased by one
// on failure, k is set to k + i - T[i], and i is set to T[i] (i > 0)
// so the k' + i' = k + i - T[i] + T[i] = k + i, the loop stalls for one time
// if i = 0, k' + i' = k + i + 1, the loop go one step forward
// so each failure stalls the loop one time, thus the complexity is O(n) + O(failure times)
// after a consecutive loop of i steps, the loop stalls at most i times
// because each failure will decrease i by one at least, 
// when i = 0, the loop will go foward again
// so the stall times of the loop is at most the same as the loop times
// the loop body will execute at most 2*n times, complexity of KMP is thus O(n)
//
int KMP(const char *S, int n, const char *W, const int *T, int m) {
  int k = 0; // start position of match in S
  int i = 0; // index to W
  while (k + i < n) {
    if (W[i] == S[k + i]) {
      if (++i == m) return k;
    }
    else {
      // though S[k+i] doesn't match W[i], there are T[i] characters that
      // match before i
      k = k + i - T[i];
      if (T[i] >= 0) i = T[i];
    }
  }
  return -1;
}

// T[i] is the rollbacking step when w[i] doesn't match
// so update T[i] when w[i-1] == W[cnd], not w[i] == W[cnd];
// the complexity anlysis is similar to KMP
int *PartialMatchTable(const char *W, int n) {
  int *T = new int[n];
  int i = 2, cnd = 0;
  T[0] = -1; T[1] = 0; // error for n = 1
  while (i < n) {
    if (W[i-1] == W[cnd]) {
      // W[0, cnd] == W[i-1-cnd, i-1]
      T[i++] = ++cnd; 
    }
    else if (cnd > 0) {
      // W[0, cnd-1] == W[i-2-cnd, i-2]
      // W[0, T[cnd]] == W[cnd-1-T[cnd], cnd-1]
      cnd = T[cnd]; 
    }
    else T[i++] = 0;
  }
  return T;
}

int KMP(const char *str, const char *w) {
  int n = strlen(str);
  int m = strlen(w);
  if (m == 0 || m > n) return -1;

  int *T = PartialMatchTable(w, m);
  int ret = KMP(str, n, w, T, m);

  delete[] T;
  return ret;
}

void Check(const char *S, const char *W, int i) {
  const char *p = strstr(S, W);
  if ((i < 0 && p != NULL) || (i >= 0 && p == NULL)) {
    printf("match error\n");
    return;
  }
  if (i < 0) return;
  for (int k = 0; W[k] != '\0'; ++k) {
    if (W[k] != S[i + k]) {
      printf("match error\n");
      break;
    }
  }
  printf("OK\n");
}

char *GenString(int n) {
  char *str = new char[n + 1];
  for (int i = 0; i < n; ++i) {
    str[i] = rand() % (127 - 32) + 32;
  }
  str[n] = '\0';
  return str;
}

char *GenSubString(const char *str, int n) {
  int i = rand() % n; // 0-n-1
  int m = 1 + rand() % (n - i); // 1 - n
  char *ptr = new char[m + 1];
  strncpy(ptr, str + i, m);
  ptr[m] = '\0';
  return ptr;
}

int main(int argc, const char *argv[]) {
  if (argc < 2) {
    printf("Usage: <cmd> <string lenght>\n");
    return -1;
  }
  srand(time(NULL));
  int n = atoi(argv[1]);
  char *S = GenString(n);
  char *W = GenSubString(S, n);
  int i = KMP(S, W);
  Check(S, W, i);
  return 0;
}

